//
// Created by Administrator on 2021/8/10.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <set>
#include <cstring>

using namespace std;

class Solution {
public:
    string longestWord(vector<string> &words) {
        unordered_set<string> dict(words.begin(), words.end());
        string ans;
        for (auto i = dict.begin(); i != dict.end(); ++i) {
            string str = *i;
            if (str.size() > ans.size() or (str.size() == ans.size() and str < ans)) {
                // 考察是否每个前缀都存在
                bool flag = true;
                for (int j = 1; j < str.size(); ++j) {
                    if (!dict.count(str.substr(0, j))) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans = str;
            }
        }
        return ans;
    }
};

struct Node {
    Node *children[26];
    int wordIndex;

    Node() {
        // 默认是无效值
        wordIndex = -1;
        memset(children, 0, sizeof(children));
    }
};

class Solution2 {
private:
    Node *root;
    // 记录满足条件的最长的单词
    string res;

    void dfs(Node *curr, vector<string> &words) {
        if (curr->wordIndex >= 0) {
            if (words[curr->wordIndex].size() > res.size()
                || (words[curr->wordIndex].size() == res.size() && words[curr->wordIndex] < res)) {
                res = words[curr->wordIndex];
            }
            for (int i = 0; i < 26; ++i) {
                if (curr->children[i] != nullptr) {
                    dfs(curr->children[i], words);
                }
            }
        }
    }

public:
    string longestWord(vector<string> &words) {
        root = new Node();

        // 插入单词
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            Node *curr = root;
            for (char c : words[i]) {
                if (curr->children[c - 'a'] == nullptr) {
                    curr->children[c - 'a'] = new Node();
                }
                curr = curr->children[c - 'a'];
            }
            curr->wordIndex = i;
        }
        // 深度优先去找结果
        for (int i = 0; i < 26; ++i) {
            if (root->children[i] != nullptr) {
                dfs(root->children[i], words);
            }
        }
        delete root;
        root = nullptr;
        return res;
    }
};

int main() {
    vector<string> words{"b", "br", "bre", "brea", "break", "breakf", "breakfa", "breakfas", "breakfast", "l", "lu",
                         "lun", "lunc", "lunch", "d", "di", "din", "dinn", "dinne", "dinner"};
    Solution2 solution;
    cout << solution.longestWord(words) << endl;
    return 0;
}
